//https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr || l2 == nullptr)
        {
            return l1 == nullptr ? l2 : l1;
        }
        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        ListNode* cur3 = nullptr;
        ListNode* head = nullptr;

        while (cur1 && cur2)
        {
            ListNode* tmp = nullptr;
            if (cur1->val < cur2->val)
            {
                tmp = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tmp = cur2;
                cur2 = cur2->next;
            }

            if (head == nullptr)
            {
                head = tmp;
                cur3 = head;
            }
            else
            {
                cur3->next = tmp;
                cur3 = cur3->next;
            }
        }

        if (cur2)
        {
            cur3->next = cur2;
        }

        if (cur1)
        {
            cur3->next = cur1;
        }

        return head;
    }
};